'''
数组
定义: 相同类型的变量组成的有序集合。
优势: 查询速度快，给出时间就能用常量时间找到元素
劣势：数组元素紧密连续存储在内存中，插入、删除元素会导致大量元素被迫移动影响整体效率
'''

class Array:
    def __init__(self, capacity):
        self.array = [None] * capacity  # 数组长度
        self.size = 0  # 下标

    def insert(self, index, element):
        '''
        版本1 思路
        在一个固定长度的数组上面增加数据 超出长度报错
        :param index: 下标
        :param element: 元素
        :return:
        '''
        # 判断访问下标是否超出范围
        if index < 0 or index > self.size:
            raise Exception("超出数组实际工作范围")
        # 从左往右依此向右挪一个单位
        for i in range(self.size - 1, -1, -1):
            self.array[i + 1] = self.array[i]
        # 腾出位置放置新的元素
        self.array[index] = element
        self.size += 1

    def resize(self):
        array_new = [None] * len(self.array) * 2
        # 从旧数组复制到新数组
        for i in range(self.size):
            array_new[i] = self.array[i]
        self.array = array_new

    def insert_v2(self, index, element):
        '''
        在一个长度数组上增加数据，如果超出长度 那么数组长度*2
        :param index: 元素下标
        :param element: 元素
        :return:
        '''
        # 判断下标是否超出长度
        if index < 0 or index > len(self.size):
            raise Exception("超出数组实际元素范围！")
        # 如果实际元素达到数组容量上限，数组则扩容
        if self.size >= len(self.array):
            pass
        # 从右向左依此向右挪一位。
        for i in range(self.size - 1, -1, -1):
            self.array[i + 1] = self.array[i]
        # 挪出的位置增加新的元素
        self.array[index] = element
        self.size += 1

    def remove(self, index):
        # 判断访问下标是否超出范围
        if index < 0 or index >= self.size:
            raise Exception("超出数组实际元素范围")
        # 从左到右依此挪动一位
        for i in range(index, self.size):
            self.array = self.array[i + 1]
        self.size -= 1

    def output(self):
        for i in range(self.size):
            print(self.array[i])

array = Array(4)
array.insert(0, 10)
print(array.output())
array.insert(0, 11)
print(array.output())
array.insert(0, 12)
print(array.output())
array.insert(0, 13)
print(array.output())
# array.insert(0, 14)
print("--------------")
array.output()